//
// Created by francklinson on 2021/5/22.
//
/*给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。*/
#include <string>
#include <queue>
#include <iostream>
#include <unordered_map>
#include <set>

using namespace std;

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> fre;
        priority_queue<pair<int, char>> q;
        for (auto &x:s) ++fre[x];
        for (auto &x:fre)
            q.emplace(x.second, x.first);
        string ans;
        while (!q.empty()) {
            // 可以直接塞字母
            if (ans.empty() or ans.back() != q.top().second) {
                auto temp = q.top();
                q.pop();
                ans.push_back(temp.second);
                if (--temp.first > 0) q.push(temp);
            } else { // 不能直接塞字母 需要塞下一个数量最多的字母
                auto temp1 = q.top();
                q.pop();
                if (q.empty()) return "";
                auto temp2 = q.top();
                q.pop();
                ans.push_back(temp2.second);
                if (--temp2.first > 0) q.push(temp2);
                q.push(temp1);
            }
        }
        return ans;
    }
};

int main() {
    Solution sol;
    cout << sol.reorganizeString("aaab") << endl;
    cout << sol.reorganizeString("accb") << endl;
    cout << sol.reorganizeString("aaabb") << endl;
    return 0;
}